Standard implementations of the Paxos state machine replication protocol, or of other state machine replication protocols, require “proposals” for how the replicated state should be changed to be sent and accepted as an indivisible unit. The proposals can include, for example, data to be written. This can make it difficult to implement the replication protocol in a wide area, since larger proposals may take a long time to transmit over low-bandwidth links, especially in the case of congestion or failures. In order to ensure liveness of the replication protocol, it is necessary to timeout a proposal transfer when it is not making progress. However, large proposals making slow progress can also timeout, preventing the proposal from being committed. In some instances, a leader elected to send proposals may lose leadership if it is having trouble transmitting proposals. Accordingly, large proposals can cause the replication system to be leaderless for indefinite periods, preventing any progress.